[Q&A] atcoderのc問題でtle

atcoderのc問題でtle

解決したいこと

Atcoderのabc354,C問題で2つだけtleになってしまう。
良ければ改善案教えてください。

該当するソースコード

#include <bits/stdc++.h>
using namespace std;
int main(void)
{
    int n;
    cin >> n;
    vector<pair<int, int>> cards(n), copys(n);
    vector<int> ans(n, -1);
    for(int i = 0; i < n; i++)
    {
        int first, second;
        cin >> first;
        cin >> second;
        cards.at(i) = make_pair(first, second);
    }
    copys = cards;
    sort(cards.rbegin(), cards.rend());
    int min = cards[0].second;
    for(int i = 1; i < n; i++)
    {
        if(min < cards[i].second) cards[i].first = -1;
        if(min > cards[i].second) 
        {
            min = cards[i].second;
        }
    }
    int sum = 0;
    for(int i = 0; i < n; i++)
    {
        if(cards[i].first != -1) sum++; 
    }
    cout << sum << endl;
    vector<int> index(n, -1);
    for(int i = 0; i < n; i++)
    {
        if(cards[i].first != -1)
        {
            auto it = find(copys.cbegin(), copys.cend(), cards[i]);
            index[i] = distance(copys.cbegin(), it);
        }
    }
    sort(index.begin(), index.end());
    for(int i = 0; i < n; i++)
    {
        if(index[i] != -1) cout << index[i] + 1 << " ";
    }
    cout << endl;
    return 0;
}

問題: https://atcoder.jp/contests/abc354/tasks/abc354_c
提出結果: https://atcoder.jp/contests/abc354/submissions/53638799

1Answer

@amate posted at 2024-05-18

毎回findするのは処理が重いので、標準入力からの読み込み時についでにindexをつけて上げればよいのでは？


#include <vector>
#include <algorithm>
#include <iostream>
#include <tuple>

using namespace std;
int main()
{
    int n;
    cin >> n;
    vector<tuple<int, int, int>> cards(n);
    for (int i = 0; i < n; i++)
    {
        int first, second;
        cin >> first;
        cin >> second;
        cards.at(i) = make_tuple(first, second, i);
    }

    sort(cards.rbegin(), cards.rend());
    vector<int> index;

    int min = std::get<1>(cards[0]);
    index.emplace_back(std::get<2>(cards[0]));  // 一番強いカードは問答無用

    for (int i = 1; i < n; i++)
    {
        const int cost = std::get<1>(cards[i]);
        if (min < cost) {
            //cards[i].first = -1;    // costが大きいので消す
        } else {
            index.emplace_back(std::get<2>(cards[i]));
        }
        if (min > cost) {
            min = cost;
        }
    }
    const int sum = static_cast<int>(index.size());
    cout << sum << endl;
    sort(index.begin(), index.end());
    for (int i : index) {
        cout << (i + 1) << " ";
    }
    cout << endl;
    return 0;
}

Comments

@ponitatenichi
Questioner
回答ありがとうございます。tupleという構造があるのですね。初めて知りました。
無事acできました！

atcoderのc問題でtle

解決したいこと

該当するソースコード

1Answer

Comments

Your answer might help someone💌

Popular Questions